from typing import List


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        #dp[i][j]代表 text1[0-i] 与 text2[0-j] 的最长公共子序列
        dp = [[0] * len(text2) for _ in range(0, len(text1))]
        #dp初始化
        if text2[0] == text1[0]:
            dp[0][0] = 1
        for i in range(1, len(text1)):
            if text2[0] == text1[i]:
                dp[i][0] = 1
            else:
                dp[i][0] = dp[i - 1][0]
        for j in range(1, len(text2)):
            if text2[j] == text1[0]:
                dp[0][j] = 1
            else:
                dp[0][j] = dp[0][j - 1]
        #dp状态转移
        for i in range(1, len(text1)):
            for j in range(1, len(text2)):
                dp[i][j] = dp[i - 1][j - 1]
                if text1[i] == text2[j]:
                    dp[i][j] += 1
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i][j])

        return dp[-1][-1]


if __name__ == "__main__":
    solution = Solution()
    res = solution.findLength(text1=[0, 0, 0, 0, 0], text2=[0, 0, 0, 0, 0])
    print(res)
